package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/power-of-three'>3 的幂(Power of Three)</a>
 * <p>给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。</p>
 * <p>整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：n = 27
 *      输出：true
 *  示例 2：
 *      输入：n = 0
 *      输出：false
 *  示例 3：
 *      输入：n = 9
 *      输出：true
 *  示例 4：
 *      输入：n = 45
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>-2^31 <= n <= 2^31 - 1</li>
 * </ul>
 * </p>
 * <b>进阶：你能不使用循环或者递归来完成本题吗？</b>
 *
 * @author c2b
 * @since 2025/4/28 11:56
 */
public class LC0326PowerOfThree_S {
    static class Solution {
        public boolean isPowerOfThree(int n) {
            // -2^31 <= n <= 2^31 - 1。
            // 此范围内：最大的3的幂为：3^19 = 1162261467。只需要判断给定的n是否为3^19的约数即可
            return n > 0 && 1162261467 % n == 0;
        }

        public boolean isPowerOfThree2(int n) {
            while (n > 0 && n % 3 == 0) {
                n /= 3;
            }
            return n == 1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPowerOfThree(27));
        System.out.println(solution.isPowerOfThree(0));
        System.out.println(solution.isPowerOfThree(9));
        System.out.println(solution.isPowerOfThree(45));
    }
}
